/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-02-26
 * Time: 22:42
 */
public class Solution {
    // DP
    // dp[i][j] 表示到达下标为 i, j  位置的不同路径的条数
    // 因为只能向下或者向右
    // 所以上边界和左边界只有一种路径到达
    // 其他位置可以由 上方或者左边到达, 所以为 上和左 之和
    public int uniquePaths(int m, int n) {
        int[][] dp=new int[m][n];
        for(int i=0;i<m;i++){
            dp[i][0]=1;
        }
        for(int i=0;i<n;i++){
            dp[0][i]=1;
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}
